/**
 * 641. 设计循环双端队列
 * 设计实现双端队列。
 *	你的实现需要支持以下操作：
 *
 *	MyCircularDeque(k)：构造函数,双端队列的大小为k。
 *	insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
 *	insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
 *	deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
 *	deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
 *	getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
 *	getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
 *	isEmpty()：检查双端队列是否为空。
 * 	isFull()：检查双端队列是否满了。
*/

// 解法一： 双数组
// head数组:头插，头删，取头
// trail数组:尾插，尾删，取尾
// cap:容量
type MyCircularDeque struct {
    head []int
    trail []int
    cap int
}

// 初始化head，trail，cap
/** Initialize your data structure here. Set the size of the deque to be k. */
func Constructor(k int) MyCircularDeque {
    return MyCircularDeque{make([]int,0), make([]int,0),k}
}

// 头插：当head数组和trail数组的长度和大于等于（应该不会大于）cap时，插入失败，反之插入成功（head数组后面追加一个value）
/** Adds an item at the front of Deque. Return true if the operation is successful. */
func (this *MyCircularDeque) InsertFront(value int) bool {
    if len(this.head) + len(this.trail) >= this.cap {
        return false
    }
    this.head = append(this.head, value)
    return true
}


// 尾插：头插：当head数组和trail数组的长度和大于等于（应该不会大于）cap时，插入失败，反之插入成功（trail数组后面追加一个value）
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
func (this *MyCircularDeque) InsertLast(value int) bool {
    if len(this.head)+len(this.trail)>=this.cap {
        return false
    }
    this.trail = append(this.trail, value)
    return true
}


// 头删：当head不为空时，去掉head数组的最后一位。当head为空，trail不为空时，去掉trail的第一位。当head和trail皆空时，删除失败
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
func (this *MyCircularDeque) DeleteFront() bool {
    if len(this.head)>0 {
        this.head = this.head[:len(this.head)-1]
        return true
    }
    if len(this.trail)>0 {
        this.trail  = this.trail[1:]
        return true
    }
    return false
}


// 尾删：当trail不为空时，去掉trail数组的最后一位。当trail为空，head不为空时，去掉head的第一位。当head和trail皆空时，删除失败
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
func (this *MyCircularDeque) DeleteLast() bool {
    if len(this.trail)>0 {
        this.trail = this.trail[:len(this.trail)-1]
        return true
    }
    if len(this.head)>0 {
        this.head = this.head[1:]
        return true
    }
    return false
}


// 取头：当head不为空时，返回head的最后一位。当head为空trail不为空时，返回trail的第一位。皆空时，取数失败，返回-1
/** Get the front item from the deque. */
func (this *MyCircularDeque) GetFront() int {
    if len(this.head)>0 {
        return this.head[len(this.head)-1]
    }
    if len(this.trail)>0 { 
        return this.trail[0]
    }
    return -1
}


// 取尾：当trail不为空时，返回trail的最后一位。当trail为空head不为空时，返回head的第一位。皆空时，取数失败，返回-1
/** Get the last item from the deque. */
func (this *MyCircularDeque) GetRear() int {
    if len(this.trail)>0 {
        return this.trail[len(this.trail)-1]
    }
    if len(this.head)>0 {
        return this.head[0]
    }
    return -1
}


// 当head和trail的和等于0时，为空，返回true，反之，返回false
/** Checks whether the circular deque is empty or not. */
func (this *MyCircularDeque) IsEmpty() bool {
    if len(this.head) + len(this.trail) == 0{
        return true
    }
    return false
}


// 当head和trail的和等于cap时，为满，返回true，反之，返回false
/** Checks whether the circular deque is full or not. */
func (this *MyCircularDeque) IsFull() bool {
    if len(this.head)+len(this.trail) == this.cap {
        return true
    }
    return false
}


/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.InsertFront(value);
 * param_2 := obj.InsertLast(value);
 * param_3 := obj.DeleteFront();
 * param_4 := obj.DeleteLast();
 * param_5 := obj.GetFront();
 * param_6 := obj.GetRear();
 * param_7 := obj.IsEmpty();
 * param_8 := obj.IsFull();
 */
 

/******************************************************************************************/


 // 解法二：双向链表

 // 双向链表结构体
 type Node struct{
    Value int
    Prev *Node
    Next *Node
}

// 双端队列结构体
// Cap: 容量
// Size: 当前存储大小
// Head: 头插，头删，取头链表
// Trail: 尾插，尾删，取尾链表
type MyCircularDeque struct {
    Cap int
    Size int
    Head *Node
    Trail *Node
}


// 初始化
/** Initialize your data structure here. Set the size of the deque to be k. */
func Constructor(k int) MyCircularDeque {
    return MyCircularDeque{k,0,nil,nil}
}


/** Adds an item at the front of Deque. Return true if the operation is successful. */
func (this *MyCircularDeque) InsertFront(value int) bool {
	// 容量已满，插入失败
    if this.Size == this.Cap{
        return false
    }

    // 当头结点不为空时，使Head.Prev指向新节点node，使新节点的Next指向当前的head节点
    node := &Node{Value:value}
    if this.Head!=nil {
        this.Head.Prev = node
        node.Next = this.Head
    }
    // 更新头结点
    this.Head = node

    // 当尾节点为空时（插入的新节点为唯一节点），更新尾节点为新节点
    if this.Trail == nil {
        this.Trail = node
    }

    // 当前容量加一，插入成功
    this.Size++
    return true
}


// 与InsertFront同理
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
func (this *MyCircularDeque) InsertLast(value int) bool {
    if this.Size == this.Cap {
        return false
    }

    node := &Node{Value:value}

    if this.Trail!=nil {
        this.Trail.Next = node
        node.Prev = this.Trail
    }
    
    this.Trail = node

    if this.Head == nil {
        this.Head = node
    }

    this.Size++

    return true
}


/** Deletes an item from the front of Deque. Return true if the operation is successful. */
func (this *MyCircularDeque) DeleteFront() bool {
	// 当前队列元素数量为零时，删除失败
    if this.Size==0 {
        return false
    }

    // 当队列只有一个元素的时候，重置该队列，删除成功
    if this.Head == this.Trail {
        this.Head = nil
        this.Trail = nil
        this.Size--
        return true
    }

    // 删除头结点
    this.Head = this.Head.Next
    this.Head.Prev = nil

    // 队列大小减一
    this.Size--

    // 删除成功
    return true
}


// 与DeleteFront 同理
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
func (this *MyCircularDeque) DeleteLast() bool {
    if this.Size==0 {
        return false
    }

    if this.Head == this.Trail {
        this.Head = nil
        this.Trail = nil
        this.Size-- 
        return true
    }

    this.Trail = this.Trail.Prev
    this.Trail.Next = nil

    this.Size--
    return true
}


/** Get the front item from the deque. */
func (this *MyCircularDeque) GetFront() int {
	// 当队列不存在元素时，取值失败，返回-1
    if this.Size ==0 {
        return -1
    }
    // 返回头结点的值
    return this.Head.Value
}


/** Get the last item from the deque. */
func (this *MyCircularDeque) GetRear() int {
	// 当队列不存在元素时，取值失败，返回-1
    if this.Size == 0{
        return -1
    }
    // 返回尾节点的值
    return this.Trail.Value
}


/** Checks whether the circular deque is empty or not. */
func (this *MyCircularDeque) IsEmpty() bool {
	// 判断队列是否存在元素
    return this.Size==0
}


/** Checks whether the circular deque is full or not. */
func (this *MyCircularDeque) IsFull() bool {
	// 判断队列的元素数量是否等于该队列的容量
    return this.Size==this.Cap
}


/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.InsertFront(value);
 * param_2 := obj.InsertLast(value);
 * param_3 := obj.DeleteFront();
 * param_4 := obj.DeleteLast();
 * param_5 := obj.GetFront();
 * param_6 := obj.GetRear();
 * param_7 := obj.IsEmpty();
 * param_8 := obj.IsFull();
 */